package zuo.algo.c05;

import zuo.algo.data.LinkedNode;
import zuo.algo.util.LinkedUtils;
import zuo.algo.util.SortUtils;

import java.util.Random;

/**
 * 01:34-将单向链表划分为左中右三部分
 */
public class Partition {

    public static LinkedNode part1(LinkedNode head, int num) {
        LinkedNode node = head;
        int size = 0;
        while (node != null) {
            size++;
            node = node.next;
        }
        int[] tempArr = new int[size];
        node = head;
        for (int i = 0; i < size; i++) {
            tempArr[i] = node.val;
            node = node.next;
        }
        int idx = 0, lessIdx = 0, greaterIdx = size - 1;
        while (idx <= greaterIdx) {
            if (tempArr[idx] < num) {
                SortUtils.swap(tempArr, idx++, lessIdx++);
            } else if (tempArr[idx] > num) {
                SortUtils.swap(tempArr, idx, greaterIdx--);
            } else {
                idx++;
            }
        }
        return LinkedUtils.constructLinkedList(tempArr);
    }

    public static LinkedNode part2(LinkedNode head, int num) {
        LinkedNode ltBegin = null, ltEnd = null, eqBegin = null, eqEnd = null, gtBegin = null, gtEnd = null;

        LinkedNode node = head;
        while (node != null) {
            if (node.val < num) {
                if (ltBegin == null) {
                    ltBegin = node;
                } else {
                    ltEnd.next = node;
                }
                ltEnd = node;
            } else if (node.val > num) {
                if (gtBegin == null) {
                    gtBegin = node;
                } else {
                    gtEnd.next = node;
                }
                gtEnd = node;
            } else {
                if (eqBegin == null) {
                    eqBegin = node;
                } else {
                    eqEnd.next = node;
                }
                eqEnd = node;
            }
            node = node.next;
        }
        LinkedNode res;
        if (ltBegin != null) {
            res = ltBegin;
            if (eqBegin != null) {
                ltEnd.next = eqBegin;
                if (gtBegin != null) {
                    eqEnd.next = gtBegin;
                }
            } else {
                if (gtBegin != null) {
                    ltEnd.next = gtBegin;
                }
            }
        } else {
            if (eqBegin != null) {
                res = eqBegin;
                if (gtBegin != null) {
                    eqEnd.next = gtBegin;
                }
            } else {
                res = gtBegin;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 1000000; i++) {
            int[] arr = SortUtils.getRandomArr(1000, 100);
            LinkedNode head = LinkedUtils.constructLinkedList(arr);
            Random random = new Random();
            int num = random.nextInt(100) + 1;
            LinkedNode res1 = part1(head, num);
            LinkedNode res2 = part2(head, num);
            LinkedNode node1 = res1;
            LinkedNode node2 = res2;
            while (node1 != null) {
                if (node1.val < num && node2.val >= num) {
                    throw new RuntimeException();
                }
                if (node1.val == num && node2.val != num) {
                    throw new RuntimeException();
                }
                if (node1.val > num && node2.val <= num) {
                    throw new RuntimeException();
                }
                node1 = node1.next;
                node2 = node2.next;
            }
            System.out.println(i);
        }
    }
}
